package com.code.test.first.link;

/**
 * https://github.com/youngyangyang04/leetcode-master/blob/master/problems/%E9%9D%A2%E8%AF%95%E9%A2%9802.07.%E9%93%BE%E8%A1%A8%E7%9B%B8%E4%BA%A4.md
 * <p>
 * 给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null 。
 * <p>
 * 图示两个链表在节点 c1 开始相交：
 */
public class Code207 {

    public static void main(String[] args) {
        ListNode headA = new ListNode(21);
        ListNode second = new ListNode(22);
        ListNode third = new ListNode(23);
        ListNode n4 = new ListNode(24);
        ListNode n5 = new ListNode(99);
        ListNode n6 = new ListNode(98);
        ListNode n7 = new ListNode(100);

        headA.setNext(second);
        second.setNext(third);
        third.setNext(n4);
        n4.setNext(n5);
        n5.setNext(n6);
        n6.setNext(n7);

        /**
         * ========================================
         */

        ListNode headB = new ListNode(11);
        ListNode secondB = new ListNode(12);
        ListNode thirdB = new ListNode(13);
        ListNode nB4 = new ListNode(14);

        headB.setNext(secondB);
        secondB.setNext(thirdB);
        thirdB.setNext(nB4);
        nB4.setNext(n4);
        n4.setNext(n5);
        n5.setNext(n6);
        n6.setNext(n7);

        ListNode tempHeadA = headA;
        ListNode tempHeadB = headB;
        while (headA != null) {
            System.out.print(headA.getVal() + "→");
            headA = headA.getNext();
        }

        System.out.println("");
        while (headB != null) {
            System.out.print(headB.getVal() + "→");
            headB = headB.getNext();
        }

        System.out.println("");

        ListNode node = getSampleNode(tempHeadA, tempHeadB);

        while (node != null) {
            System.out.print(node.val + "→");
            node = node.next;
        }
        System.out.println("");

    }

    /**
     * pA走过的路径为A链+B链
     *
     * pB走过的路径为B链+A链
     *
     * pA和pB走过的长度都相同，都是A链和B链的长度之和，相当于将两条链从尾端对齐，如果相交，则会提前在相交点相遇，如果没有相交点，则会在最后相遇。
     */
    public static ListNode getSampleNode(ListNode headA, ListNode headB) {
        ListNode a = headA;
        ListNode b = headB;
        while (a != b) {
            a = a != null ? a.next : headB;
            b = b != null ? b.next : headA;
        }
        return a;
    }

    public static ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode curA = headA;

        ListNode curB = headB;

        int lenA = 0;
        int lenB = 0;
        while (curA != null) {
            lenA++;
            curA = curA.next;
        }

        while (curB != null) {
            lenB++;
            curB = curB.next;
        }

        /**
         * 基本逻辑是，链表从某个相交点开始，后面的节点都是相同的
         * 所以先计算出2个链表的长度，然后让长的链表先走长度差，然后一起走，直到有相同的节点
         *
         */
        curA = headA;
        curB = headB;
        //链表A比较长
        if (lenA > lenB) {
            int gap = lenA - lenB;
            while (gap > 0) {
                curA = curA.next;
                gap--;
            }
        } else {
            int gap = lenB - lenA;
            while (gap > 0) {
                curB = curB.next;
                gap--;
            }
        }

        while (curA != null && curB != null) {
            if (curA == curB) {
                return curA;
            }
            curA = curA.next;
            curB = curB.next;
        }

        return null;
    }


}
